(U) The present invention relates, in general, to measuring and testing and, in particular, to testing of apparatus (i.e., a randomizer).
(U) The operation of a wide range of devices is based on a number that should not be easy to predict (e.g., lottery devices, cryptographic devices, etc.). An owner of a lottery device makes money by luring players to wager a small amount of money in hopes of winning a large amount of money. If the number of lottery winners exceeds a certain percentage of the players, where the percentage is based on wager amount and prize value, then the owner loses money. If the output of the lottery device is hard to predict then fewer players will win and the owner profits by keeping a higher percentage of the wagers. This analysis applies by analogy to a cryptographic device, but the stakes may be much higher (e.g., personal security, national security, etc.).
(U) A number that is generated in a manner that is truly random is a number that is independent of any other number that is generated. In other words, any number that is produced by a device that generates numbers that are truly random generates numbers where any number produced is just as likely to be produced as any other number. That is, no number is more likely to be produced than any other number. Therefore, someone cannot predict with more certainty than a guess what the next number will be based on previously generated numbers. There is always a chance, or probability, that a person will guess correctly. The probability may be lowered, or reduced to nearly zero, by increasing the range from which the number is generated. For example, it is more difficult to guess a number in the range of 1 to 100 than 1 to 10. However, increasing the number range increases the complexity and cost of the device. So, the designer should use the widest range of numbers that is appropriate for the application. A wider range of numbers will be used in a cryptographic device used to protect sensitive information than in a lottery device for a low dollar prize.
(U) A device that attempts to produce a random number is often referred to as a randomizer. Typically, randomizers rely on one or more sources of random data (e.g., timing of random events as compared to a threshold, random natural processes, etc.). The sources of random data are typically connected to a scrambling device that mixes the random data in some complex fashion to achieve a degree of uniformity in the distribution of the output of the randomizer. Typically, randomizers produce an m-bit block of random data.
(U) Pseudo-random number generators are not based on a source of random data but on a deterministic function that is believed to be adequate in both complexity and cycle length for the proposed application. (e.g., screen-saver movements, games of chance for entertainment, etc.).
(S) To insure that a randomizer produces outputs that are sufficiently random, the outputs are typically tested by either estimating the entropy present in the outputs, performing statistical tests on the outputs, or both. There are several different mathematical definitions for entropy which produce different results. Statistical tests are good at determining whether or not a randomizer is bad but not whether or not a randomizer is good. That is, failing a statistical test (e.g., percentage of ones and zeros, frequency of occurrence of a particular pattern, etc.) indicates that the randomizer is not producing random bits, but passing the statistical test does not, necessarily, indicate that the output is sufficiently random for the proposed application. The present invention is a method of testing a randomizer in a manner that is not based on estimating entropy or traditional statistical tests.
(U) U.S. Pat. No. 4,977,596, entitled xe2x80x9cCRYPTOGRAPHIC SYNCHRONIZATION RECOVERY BY MEASURING RANDOMNESS OF DECRYPTED DATA,xe2x80x9d discloses a device for and method of determining whether or not two cryptographic devices that are communicating with one another are in synchronization by performing a statistical test of ones density (i.e., the percentage of ones and zeros) at the output of the decryptor. The present invention does not rely solely on the ones density statistical test to determine if the output of a randomizer is sufficiently random. U.S. Pat. No. 4,977,596 is hereby incorporated by reference into the specification of the present invention.
(U) U.S. Pat. No. 5,581,561, entitled xe2x80x9cRANDOM BIT DIAGNOSTIC FOR A HIGH RESOLUTION MEASUREMENT SYSTEM,xe2x80x9d discloses a device for and method of determining whether or not a bit of a word is stuck at a zero or a one by logically combining test words with the output. The present invention does not employ the method of U.S. Pat. No. 5,581,561. U.S. Pat. No. 5,581,561 is hereby incorporated by reference into the specification of the present invention.
(U) U.S. Pat. No. 6,076,097, entitled xe2x80x9cSYSTEM AND METHOD FOR GENERATING RANDOM NUMBERS,xe2x80x9d discloses a device for and method of producing random data from one source of random data, mixing the random data, and performing chi-squared and compression tests on the data to determine if the data is sufficiently random. The present invention does not rely on chi-squared and compression tests to determine if the output of a randomizer is sufficiently random. U.S. Pat. No. 6,076,097 is hereby incorporated by reference into the specification of the present invention.
(U) It is an object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data.
(S) It is another object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data by determining the probability that an output of the randomizer will reoccur.
(S) It is another object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data by determining the minimum number of guesses one would expect to have to make to correctly determine an output of the randomizer.
(S) It is another object of the present invention to test the sufficiency of an output of a randomizer that is based on at least one source of random data by determining the probability that an output of the randomizer will reoccur and by determining the minimum number of guesses one would expect to have to make to correctly determine an output of the randomizer.
(S) The first step of the method is receiving, for each source of probabilistic data in a randomizer, a probability of occurrence of each possible state of the source of probabilistic data.
(S) The second step of the present method is raising each result of the first step to a power of two.
(S) The third step of the present method is generating a row vector a that includes the results of the second step.
(S) The fourth step of the present method is receiving the probability that each possible state transitions to each of the other possible states.
(S) The fifth step of the present method is raising each result of the fourth step to a power of two.
(S) The sixth step of the present method is generating a matrix B that includes the results of the fifth step, where each row of B represents one of the possible states from which a transition is made, where each column of B represents one of the possible states to which a transition is made, and where each numerical entry in B represents the square of the transition probability from the state represented by the row to the state represented by the column for which the entry intersects.
(S) The seventh step of the present method is generating a column vector c, where the number of entries in c is equal to the number of possible states in the probabilistic data, and where each entry in c is a one.
(S) The eighth step of the present method is computing S(P)=a(B{circumflex over ( )}(Lxe2x88x921))c for each at least one source of probabilistic data, where L is a number of outputs of probabilistic data processed by the probabilistic randomizer to produce m bits of output.
(S) If there are more than one result in the eighth step, then the ninth step of the present method is forming a product of all of the results of the eighth step and calling the result S(P). If there is only one result produced in the eighth step, then S(P) remains as defined in the eighth step.
(S) The tenth step of the present method is computing S(Q)=(xc2xd{circumflex over ( )}m) [1+(2{circumflex over ( )}mxe2x88x921)S(P)]. S(Q) is the probability that the randomizer produces the same m-bit output block at two arbitrary times.
(S) The eleventh step of the present method is declaring the probabilistic randomizer acceptable if S(Q) is below a user-definable value. Otherwise, declaring the probabilistic randomizer unacceptable.
(S) In alternate embodiment of the present method, the first ten steps of the method described above are performed along with the following steps: comparing 2{circumflex over ( )}m and 4/(3S(Q)) and setting x to whichever is smallest; computing W(Q)=(⅙) [3x+3xe2x88x92(3(x{circumflex over ( )}2xe2x88x921)(xS(Q)xe2x88x921)){circumflex over ( )}0.5]; and declaring the probabilistic randomizer acceptable if W(Q) is above a user-definable value, otherwise, declaring the probabilistic randomizer unacceptable.
(S) In a second alternate embodiment of the present method, the first twelve steps of the alternate embodiment are performed along with the step of declaring the probabilistic randomizer acceptable if S(Q) is below a user-definable value and W(Q) is above a user-definable value, otherwise declaring the probabilistic randomizer unacceptable.